#pragma once
#include <utility>
#include <vector>
#include <functional>
#include <cassert>

// 手动调用sort的set, 基于vector的实现，性能更高
template <typename Key, typename Compare>
class LazySet
{
public:
    class const_iterator
    {
    public:
        bool operator==(const const_iterator &o) const
        {
            assert(&set_ == &o.set_);
            return pos_ == o.pos_;
        }

        // bool operator==(const iterator &o) const
        // {
        //     assert(&set_ == &o.set_);
        //     return pos_ == o.pos_;
        // }

        bool operator!=(const const_iterator &o) const
        {
            return !(*this == o);
        }

        const_iterator(const const_iterator &o) 
            : set_(o.set_)
            , pos_(o.pos_)
        {
        }
        const_iterator &operator=(const const_iterator &o) 
        {
            assert(&set_ == &o.set_);
            pos_ = o.pos_;
            return *this;
        }

        // bool operator!=(const iterator &o) const
        // {
        //     return !(*this == o);
        // }

        int operator-(const const_iterator &o) const
        {
            return pos_ - o.pos_;
        }
        const_iterator operator+(int diff) const
        {
            return const_iterator(set_, pos_+diff);
        }
        const_iterator &operator++()
        {
            ++pos_;
            return *this;
        }
        const_iterator &operator--()
        {
            --pos_;
            return *this;
        }
        const Key *operator->() const
        {
            return &(**this);
            // return &set_.keys_.at(set_.indexs_.at(pos_));
        }
        const Key &operator*() const
        {
            return set_.keys_.at(set_.indexs_.at(pos_));
        }
    private:
        const LazySet &set_;
        int pos_;
        friend class LazySet;
    private:
        const_iterator(const LazySet &m, int pos)
            : set_(m)
            , pos_(pos)
        {
        }
    };

    // class iterator
    // {
    // public:
    //     bool operator==(const iterator &o) const
    //     {
    //         assert(&set_ == &o.set_);
    //         return pos_ == o.pos_;
    //     }

    //     bool operator==(const const_iterator &o) const
    //     {
    //         assert(&set_ == &o.set_);
    //         return pos_ == o.pos_;
    //     }

    //     bool operator!=(const iterator &o) const
    //     {
    //         return !(*this == o);
    //     }

    //     bool operator!=(const const_iterator &o) const
    //     {
    //         return !(*this == o);
    //     }

    //     const_iterator operator+(int diff) const
    //     {
    //         return const_iterator(set_, pos_+diff);
    //     }
    //     iterator &operator++()
    //     {
    //         ++pos_;
    //         return *this;
    //     }
    //     iterator &operator--()
    //     {
    //         --pos_;
    //         return *this;
    //     }
    //     const Key &operator*() const
    //     {
    //         return set_.keys_.at(pos_);
    //     }
    // private:
    //     LazySet &set_;
    //     int pos_;
    //     friend class LazySet;
    // private:
    //     iterator(LazySet &m, int pos)
    //         : set_(m)
    //         , pos_(pos)
    //     {
    //     }
    // };

    LazySet(Compare comp = Compare())
        : less_(comp)
    {}
    // const_iterator find(const Key& k) const {
    //     auto iter = const_cast<LazySet*>(this)->find(k);
    //     return const_iterator(*this, iter.pos_);
    // }
    const_iterator find(const Key& k) const {
        if (0 == size()) {
            return end();
        }
        int left = 0;
        int right = keys_.size() - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (less_(value(mid), k)) {
                left = mid+1;
            }
            else if (less_(k, value(mid))){
                right = mid-1;
            }
            else {
                return iterator(*this, mid);
            }
        }
        return this->end();
    }

    template<typename Value>
    const_iterator _lower_bound(const Value &v) const {
        int left = 0;
        int right = keys_.size();
        while (left < right) {
            int mid = (left + right) >> 1;
            if (less_(value(mid), v)) {
                left = mid+1;
            }
            else if (less_(v, value(mid))){
                right = mid;
            }
            else {
                return const_iterator(*this, mid);
            }
        }
        return const_iterator(*this, left);
    }

    template<typename Value>
    typename std::enable_if<!std::is_same_v<Key, Value>, const_iterator>::type lower_bound(const Value &v) const {
        if (0 == size()) {
            return end();
        }
        return _lower_bound(v);
    }

    const_iterator lower_bound(const Key &k) const {
        if (0 == size()) {
            return end();
        }
        return _lower_bound(k);
        // int left = 0;
        // int right = keys_.size();
        // while (left < right) {
        //     int mid = (left + right) >> 1;
        //     if (less_(value(mid), k)) {
        //         left = mid+1;
        //     }
        //     else if (less_(k, value(mid))){
        //         right = mid;
        //     }
        //     else {
        //         return const_iterator(*this, mid);
        //     }
        // }
        // return const_iterator(*this, left);
    }

    const_iterator upper_bound(const Key &k) const {
        if (0 == size()) {
            return end();
        }
        int left = 0;
        int right = keys_.size();
        int mid = (left + right) >> 1;
        while (left < right) {
            if (less_(k, value(mid))){
                right = mid;
            }
            else {
                left = mid+1;
            }

            mid = (left + right) >> 1;
        }
        return const_iterator(*this, left);
    }

    // const_iterator begin()
    // {
    //     return const_iterator(*this, 0);
    // }

    const_iterator begin() const
    {
        return const_iterator(*this, 0);
    }

    // const_iterator end()
    // {
    //     return const_iterator(*this, keys_.size());
    // }

    const_iterator end() const
    {
        return const_iterator(*this, keys_.size());
    }

    const_iterator rbegin()
    {
        return const_iterator(*this, int(keys_.size()) - 1);
    }

    const_iterator rend()
    {
        return const_iterator(*this, -1);
    }

    void insert(const Key &k)
    {
        keys_.emplace_back(std::forward<Key>(k));
    }

    void emplace(Key &&k)
    {
        keys_.emplace_back(std::forward<Key>(k));
    }

    // 只能调用一次
    void sort()
    {
        assert(0 == indexs_.size());
        indexs_.reserve(keys_.size());
        for (size_t i = 0; i < keys_.size(); ++i) {
            indexs_.push_back(i);
        }
        std::sort(indexs_.begin(), indexs_.end(), [this](int i1, int i2){
            return less_(keys_[i1], keys_[i2]);
        });
    }
    size_t size() const
    {
        return keys_.size();
    }
    bool contains(const Key& k) const {
        auto iter = find(k);
        assert(iter != this->end());
        return iter->second;
    }
    bool contains(const Key& k) {
        auto iter = find(k);
        assert(iter != this->end());
        return iter->second;
    }
private:
    std::vector<int> indexs_;
    std::vector<Key> keys_;
    Compare less_;
private:
    const Key &value(int i) const {
        return keys_[indexs_[i]];
    }
};

